package com.cn.algorithm02.class16;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/***
 * @author: hels
 * @description: 二位数组中的岛问题- https://leetcode.cn/problems/number-of-islands/
 *
 **/
public class C04_NumberOfIslands {
    //    方法一：递归感染
    public int numIslands1(char[][] grid) {
        int nums = 0;
        int m = grid.length;
        int n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    nums++;
                    infect(grid, i, j);
                }
            }
        }
        return nums;
    }

    private void infect(char[][] grid, int i, int j) {
        if (i < 0 || i == grid.length || j < 0 || j == grid[0].length || grid[i][j] != '1') {
            return;
        }
        grid[i][j] = '2';
        infect(grid, i - 1, j);
        infect(grid, i + 1, j);
        infect(grid, i, j - 1);
        infect(grid, i, j + 1);
    }

    //    方法二：并查集，使用MAP集合
    public int numIslands2(char[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        Dot[][] dots = new Dot[rows][cols];
        List<Dot> list = new ArrayList<>();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    dots[i][j] = new Dot();
                    list.add(dots[i][j]);
                }
            }
        }

        UnionFind1<Dot> uf = new UnionFind1<>(list);
//        首先将第一行第一列进行合并操作，然后在进行其他行列合并（只考虑节点左上两个方向）
        for (int i = 1; i < cols; i++) {
            if (grid[0][i - 1] == '1' && grid[0][i] == '1') {
                uf.union(dots[0][i - 1], dots[0][i]);
            }
        }

        for (int i = 1; i < rows; i++) {
            if (grid[i - 1][0] == '1' && grid[i][0] == '1') {
                uf.union(dots[i - 1][0], dots[i][0]);
            }
        }

        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                if (grid[i][j] == '1') {
                    if (grid[i - 1][j] == '1') {
                        uf.union(dots[i][j], dots[i - 1][j]);
                    }
                    if (grid[i][j - 1] == '1') {
                        uf.union(dots[i][j], dots[i][j - 1]);
                    }
                }
            }

        }
        return uf.size();
    }

    public static class Dot {
    }

    public static class Node<V> {
        private V value;

        public Node(V v) {
            value = v;
        }
    }

    public static class UnionFind1<T> {
        private HashMap<T, Node<T>> nodes;
        private HashMap<Node<T>, Node<T>> parents;
        private HashMap<Node<T>, Integer> sizeMap;

        public UnionFind1(List<T> lists) {
            nodes = new HashMap<>();
            parents = new HashMap<>();
            sizeMap = new HashMap<>();
            for (T t : lists) {
                Node<T> node = new Node<>(t);
                nodes.put(t, node);
                parents.put(node, node);
                sizeMap.put(node, 1);
            }
        }

        //      寻找祖先，同时做路径压缩
        public Node<T> find(Node<T> node) {
            Stack<Node<T>> stack = new Stack<>();
            while (node != parents.get(node)) {
                stack.push(node);
                node = parents.get(node);
            }
            while (!stack.isEmpty()) {
                Node<T> pop = stack.pop();
                parents.put(pop, node);
            }
            return node;
        }

        //        进行域合并
        public void union(T a, T b) {
            Node<T> ahead = find(nodes.get(a));
            Node<T> bhead = find(nodes.get(b));
            if (ahead != bhead) {
                int aSize = sizeMap.get(ahead);
                int bSize = sizeMap.get(bhead);
                Node<T> big = aSize >= bSize ? ahead : bhead;
                Node<T> small = big == ahead ? bhead : ahead;
                parents.put(small, big);
                sizeMap.put(big, aSize + bSize);
                sizeMap.remove(small);
            }
        }

        public int size() {
            return sizeMap.size();
        }

    }

    //    方法三：并查集，使用数组。
//二维坐标ij处为'1'，通过坐标转换唯一值，然后通过唯一值在一位数组中的父子关系，即可转换成并查集
    public int numIslands3(char[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        UnionFind2 uf = new UnionFind2(grid);
        for (int i = 1; i < col; i++) {
            if (grid[0][i - 1] == '1' && grid[0][i] == '1') {
                uf.union(0, i - 1, 0, i);
            }
        }
        for (int i = 1; i < row; i++) {
            if (grid[i - 1][0] == '1' && grid[i][0] == '1') {
                uf.union(i - 1, 0, i, 0);
            }
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (grid[i][j] == '1') {
                    if (grid[i - 1][j] == '1') {
                        uf.union(i, j, i - 1, j);
                    }
                    if (grid[i][j - 1] == '1') {
                        uf.union(i, j, i, j - 1);
                    }
                }
            }

        }
        return uf.size();
    }

    public static class UnionFind2 {
        private int[] parents;
        private int[] size;
        private int[] help;
        private int sets;
        private int cols;

        public UnionFind2(char[][] grid) {
            cols = grid[0].length;
            int N = grid.length * cols;
            parents = new int[N];
            size = new int[N];
            help = new int[N];
            sets = 0;
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] == '1') {
                        int idx = index(i, j);
                        parents[idx] = idx;
                        size[idx] = 1;
                        sets++;
                    }
                }
            }
        }

        //        通过二维坐标寻找一维数组中的祖先节点；同时做路径压缩
        public int findAncesstor(int r, int c) {
            int idx = index(r, c);
            int hi = 0;
            while (idx != parents[idx]) {
                help[hi++] = idx;
                idx = parents[idx];
            }
            for (hi--; hi >= 0; hi--) {
                parents[help[hi]] = idx;
            }
            return idx;
        }

        //        通过二维坐标进行合并
        public void union(int r1, int c1, int r2, int c2) {
            int ahead = findAncesstor(r1, c1);
            int bhead = findAncesstor(r2, c2);
            if (ahead != bhead) {
                int aSize = size[ahead];
                int bSize = size[bhead];
                int big = aSize >= bSize ? ahead : bhead;
                int small = big == ahead ? bhead : ahead;
                parents[small] = big;
                size[big] = aSize + bSize;
                sets--;
            }
        }

        //        通过二维坐标获取数组坐标
        public int index(int row, int col) {
            return row * cols + col;
        }

        public int size() {
            return sets;
        }

    }


}
